package com.tgy.algorithm.base._堆;

import java.util.Comparator;
import java.util.HashMap;

public class Heap<V> {

    private V[] datas;
    private HashMap<V,Integer> locations;
    private int index;
    private int size;
    private Comparator<V> comparator;

    Heap(int size,Comparator<V> comparator) {
       datas = (V[]) new Object[size];
       this.index = 0;
       this.size = size;
       this.locations = new HashMap<>();
       this.comparator = comparator;
    }

    public void offer(V value) {
        if (this.index >= this.size) {
            throw new RuntimeException("heap is full");
        }

        this.datas[this.index++] = value;
        heapInsert(value,this.index - 1);
    }

    public V poll() {
        if (this.isEmpty()) {
            throw new RuntimeException("heap is empty");
        }
        V ret = this.datas[0];
        this.datas[0] = this.datas[this.index - 1];
        this.index--;
        heapify(0);
        // 更新节点的位置，如果删除了，就设置为-1，后面可以查询是否之前加进过heap
        this.locations.put(ret,-1);
        return ret;
    }

    public boolean isEmpty() {
        return this.index == 0;
    }

    private void heapInsert(V value,int index) {
        int idx = index;
        int parentIdx = (idx - 1) / 2;
        // 这里必须排除idx大于0，因为位置是在最后交换的，在idx等于0的时候，还说之前的值与value比较
        // && this.comparator.compare(value,this.datas[parentIdx]) < 0
        while (idx > 0) {
            V parentValue = this.datas[parentIdx];
            if (this.comparator.compare(value,parentValue) >= 0) {
                break;
            }
            this.datas[idx] = parentValue;
            this.locations.put(parentValue,idx);

            idx = parentIdx;
            parentIdx = (idx - 1) / 2;
        }

        this.datas[idx] = value;
        this.locations.put(value,idx);
    }


    private void heapify(int idx) {
        int leftIndex;
        V changeVal = this.datas[idx];
        while (true) {
            leftIndex = (idx << 1) + 1;
            if (leftIndex >= this.index) {
                break;
            }

            int minIndex = leftIndex+1 >= this.index? leftIndex:(
                    this.comparator.compare(this.datas[leftIndex],this.datas[leftIndex+1]) <= 0? leftIndex:
                    leftIndex+1);
            V minVal = this.datas[minIndex];
            if (this.comparator.compare(changeVal,minVal) <= 0 ) {
                break;
            }
            this.datas[idx] = minVal;
            // 更新节点的位置
            this.locations.put(minVal,idx);
            idx = minIndex;
        }

        this.datas[idx] = changeVal;
        this.locations.put(changeVal,idx);
    }

    public void updateValue(V value,V newValue) {
        Integer idx = this.locations.get(value);
        if (idx == null || idx <= 0) {
            // 不存value
            return;
        }
        this.locations.put(value,-1);
        this.datas[idx] = newValue;
        this.heapInsert(newValue,idx);
        this.heapify(idx);
    }

    public static void main(String[] args) {
        Heap<Integer> minHeap = new Heap<>(10, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        minHeap.offer(4);
        minHeap.offer(3);
        minHeap.offer(2);
        minHeap.offer(1);
        minHeap.offer(5);
        minHeap.offer(7);
        minHeap.offer(6);
        System.out.println(minHeap);
        /**
         *              1
         *           2     3
         *         4   5  6  7
         *
         *             0
         *         4         1
         *      10  5     7     6
         */
        minHeap.updateValue(3,0);
        minHeap.updateValue(2,10);
        while (!minHeap.isEmpty()) {
            Integer value = minHeap.poll();
            System.out.println(value);
        }
    }
}
